package 回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-25 23:00
 **/
public class 括号生成 {
    List<String> res = new LinkedList<>();
    char[] choice = {'(', ')'};

    public List<String> generateParenthesis(int n) {
        //java字符串回溯用stringbuilder .deleteCharAt(index)删除最后一个元素
//        char[] trace = new char[2*n];
//        for(int i=0;i<trace.length;i++)
//            trace[i]='0';
        StringBuilder sb = new StringBuilder(2 * n);

        backtrace(sb, n, n, 0, 2 * n);
        return res;

    }

    //leftKuo:可用的左括号
    //rightKuo:可用的右括号
    void backtrace(StringBuilder trace, int leftKuo, int rightKuo, int index, int size) {

        int i;


        //base case
        if (leftKuo == 0 && rightKuo == 0) {
            res.add(new String(trace));
            return;
        }

        //排除不合法选择（剪枝）
        if (leftKuo < 0 || rightKuo < 0)
            return;
        //排除不合法选择（剪枝）
        if (rightKuo < leftKuo)
            return;


        trace.append('(');
        backtrace(trace, leftKuo - 1, rightKuo, index + 1, size);
        //撤销
        trace.deleteCharAt(index);

        trace.append(')');
        backtrace(trace, leftKuo, rightKuo - 1, index + 1, size);
        //撤销
        trace.deleteCharAt(index);


    }

    boolean isValid(StringBuilder trace, char kuohao, int index, int size) {
        int leftKuoNum = 0;
        int rightKuoNum = 0;
        int i, j;
        trace.append(kuohao);


        for (i = 0; i <= index; i++) {
            if (trace.charAt(index) == '(')
                leftKuoNum++;
            if (trace.charAt(index) == ')')
                rightKuoNum++;
            if (leftKuoNum < rightKuoNum) {
                return false;
            }

        }
        if (size == trace.length())
            if (leftKuoNum != rightKuoNum) {
                return false;
            }

        return true;

    }


    public static void main(String[] args) {
        括号生成 test = new 括号生成();

        System.out.println(test.generateParenthesis(4));


    }


}

